Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Minimum Area Rectangle

Problem Statement

Given an array of points in the X-Y plane points where points[i] = [xi, yi], return the minimum area of a rectangle formed from these points. The sides of the rectangle should be parallel to the X and Y axes. If there is not any such rectangle, return 0.

Examples

  1. Example 1:

    • Input:: points = [[1,2],[2,1],[1,0],[0,1]]
    • Expected Output:: 0
    • Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.
  2. Example 2:

    • :Input:: points = [[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]]
    • :Expected Output:: 2
    • :Justification:: These points form a rectangle with corners at [3,1], [4,1], [4,3], and [3,3]. This rectangle's area is 2, making it the smallest possible area from these points.
  3. Example 3:

    • :Input:: points = [[1,1],[2,2],[3,3]]
    • :Expected Output:: 0
    • :Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.

Solution

To solve this problem, we will use a hash set to efficiently check whether a pair of points that could form the opposite corners of a rectangle exist. The core idea is to iterate through all possible pairs of points and use these as potential opposite corners of a rectangle. For each pair, we check if the other two corners (which complete the rectangle) are present in our set of points. This approach works well because checking for the existence of a point in a hash set is an O(1) operation, making the overall algorithm efficient.

The effectiveness of this approach lies in its ability to quickly determine potential rectangles by focusing on opposite corners. Since the sides of the rectangle are parallel to the axes, the X and Y coordinates of the corners provide a straightforward way to identify the missing corners if two opposite ones are known. This method is efficient for sparse point sets where not every combination of points forms a rectangle, thereby reducing unnecessary checks.

Step-by-Step Algorithm

  1. Initialize a Set:

    • Create an empty set to store all the input points for quick lookup. This set will help us check the existence of points in constant time.
  2. Iterate Through All Pairs of Points:

    • Use a nested loop to iterate through every pair of points from the input. These points are considered as potential opposite corners of a rectangle.
  3. Check for Potential Rectangles:

    • For each pair of points (p1, p2) being considered, ensure they are not on the same horizontal or vertical line, i.e., p1.x != p2.x && p1.y != p2.y.This check is crucial because, for a rectangle formed with sides parallel to the axes, opposite corners must have different x and y coordinates.
  4. Calculate the Other Two Corners:

    • For a pair of points (p1, p2) that passes the previous check, calculate the coordinates of the other two corners of the potential rectangle. These coordinates are (p1.x, p2.y) and (p2.x, p1.y).
  5. Check for the Existence of the Other Two Corners:

    • Use the set created in step 1 to check if both of these calculated points exist. If both points are present in the set, it confirms the presence of a rectangle.
  6. Calculate the Rectangle's Area:

    • If a rectangle is confirmed, calculate its area by multiplying the absolute difference in x-coordinates by the absolute difference in y-coordinates of any two adjacent corners.
  7. Track the Minimum Area:

    • Maintain a variable to keep track of the minimum area of all rectangles found. Update this variable whenever a smaller area is calculated.
  8. Return the Result:

    • After iterating through all pairs of points, return the minimum area found. If no rectangle was formed (the minimum area was not updated), return 0.

Algorithm Walkthrough

Let's consider the Input: nums = [[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]].

  1. Convert Points to a Set: First, all points are added to a set for efficient lookup. This step is essential for quickly determining if the complementary points (other two corners) of a rectangle exist.

  2. Iterate Over All Pairs of Points: We compare each pair of points to see if they can potentially form opposite corners of a rectangle.

  • Process [0, 1]:
    • Pair [[0,1],[0,3]]: Not valid because they share the same x-coordinate. Opposite corners of a rectangle must have different x and y coordinates.
    • Pair [[0,1],[3,1]]: Not valid because they share the same y-coordinate. Opposite corners of a rectangle must have different x and y coordinates.
    • Pair [[0,1],[3,3]]: This is a potential pair of opposite corners. We look for points [0,3] and [3,1], which exist. Area = (3-0) * (3-1) = 6.
    • Pair [[0,1],[4,1]]: Not valid because they share the same y-coordinate.
    • Pair [[0,1],[4,3]]: This is a potential pair, but it essentially outlines the same rectangle as [[0,1],[3,3]] and [[4,1],[3,3]], only larger, if considering [0,3] and [4,1] as the other two points. Area = (4-0) * (3-1) = 8.
  • Process [0, 3]:
    • Pair [[0,3],[3,1]]: This is a potential pair of opposite corners. We look for points [0,1] and [3,3], which exist. Area = (3-0) * (3-1) = 6.
    • Pair [[0,3],[3,3]]: Not valid because they share the same y-coordinate.
    • Pair [[0,3],[4,1]]: This is a potential pair of opposite corners. We look for points [0,1] and [4,3], which exist. Area = (4-0) * (3-1) = 8.
    • Pair [[0,3],[4,3]]: Not valid because they share the same y-coordinate.
  • Process [3, 1]:
    • Pair [[3,1],[3,3]]: Not valid because they share the same x-coordinate.
    • Pair [[3,1],[4,1]]: Not valid because they share the same y-coordinate.
    • Pair [[3,1],[4,3]]: This is a potential pair of opposite corners. We look for points [3,3] and [4,1], which exist. Area = (4-3) * (3-1) = 2.
  • Process [3, 1]:
    • Pair [[3,3],[4,1]]: This is a potential pair of opposite corners. We look for points [3,1] and [4,3], which exist. Area = (4-3) * (3-1) = 2.
    • Pair [[3,3],[4,3]]: Not valid because they share the same y-coordinate.
  • Process [4, 1]:
    • Pair [[4,1],[4,3]]: Not valid because they share the same x-coordinate.
  1. Determine the Smallest Area: From the valid rectangles identified, the one formed by the points [3,1], [4,3], [3,3], and [4,1] has the smallest area of 2. This is the minimum area rectangle that can be formed with the given points.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is primarily determined by the double loop used to iterate through all pairs of points, which gives us , where n is the number of points. For each pair, we perform a constant time operation to check if the complementary points forming the rectangle exist in the set. Thus, the overall time complexity remains .

Space Complexity

The space complexity is , where n is the number of points. This is due to the storage of all points in a hash set (or an equivalent data structure) to allow for constant time lookups. The space used by the set is directly proportional to the number of points, thus making the space complexity linear.

Minimum Area Rectangle (medium)
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity